/*-------------------------------------------------------------------------
 - Copyright (c) 2024-2025 [XD-AMCC TEAM]
 - [XD-AMCC] is licensed under Mulan PSL v2.
 - You can use this software according to the terms and conditions of the Mulan PSL v2.
 - You may obtain a copy of Mulan PSL v2 at:
 -          http://license.coscl.org.cn/MulanPSL2
 - THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES
 - OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 - TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 - See the Mulan PSL v2 for more details.
 ------------------------------------------------------------------------*/


/**
 * @file
 * @brief Interface of the generic class list, list-node, list-iterator.
 *
 * This list is a double linked circular list and its app data
 * is treated as a 'void*' pointer.
 *
 * This list and list-iterator are generic types.
 *
 * @author  WXQ#XDU
 * @date    2024.11
 */

#pragma once

#ifndef AMCC_LIST_H
#define AMCC_LIST_H

#include "amcc_config.h"

AMCC_DECL_BEGIN

/// @name API of class list-node
/// @{

/**
 * @brief Type of app-data stored in a list node.
 * The memory of app-data is allocated by caller,
 * and can be free by list_clean().
 *
 * @see list_init()
 */
typedef void * t_list_app_value;

/**
 * @brief Class list node.
 *
 * @note Caller should not access members directly, or
 *  user this type.
 */
typedef struct amcc_list_node {
    struct amcc_list_node * pPrev; //!< pointer to previous node
    struct amcc_list_node * pNext; //!< pointer to next node

    /// app-data, often a pointer to data body
    t_list_app_value       pValue;
} t_list_node , * t_list_node_ptr;

/// Get the app-value stored in a list node
#define list_node_get_value(pNode) (NULL == (pNode) ? NULL : (pNode)->pValue)

/// Change the app-value stored in a list node
#define list_node_set_value(pNode, ptr2Value)  do{if(NULL != (pNode)) (pNode)->pValue = ptr2Value;}while(0)

/// Get the app-value stored in the previous node of pNode
#define list_node_get_prev(pNode)  (NULL == (pNode) ? NULL : (pNode)->pPrev)

/// Get the app-value stored in the next node of pNode
#define list_node_get_next(pNode)  (NULL == (pNode) ? NULL : (pNode)->pNext)

/// @}
// -----------------------------------------------------------------------


// -----------------------------------------------------------------------
/// @name API of class list
/// @{

/**
 * @brief Type of functions to destroy app-data in a list node.
 *
 * The parameter is the pointer to app-data,
 * and NULL(0) is accepted.
 */
typedef void (*t_listfunc_free_appdata)(t_list_app_value);

/**
 * @brief Class list of AMCC.
 *
 * An instance of this class is a double linked list.
 */
typedef struct amcc_list {
    int length;         //!< the number of elements in list

    /// This "holder" just is a guard node.
    ///
    /// Its prev points to the last node,
    /// its next points to the first node.
    t_list_node holder;

    /// A pointer to a function which destroy app data in a node.
    t_listfunc_free_appdata fp_free_appdata;
} t_list, * t_list_ptr;


/**
 * @brief Creates and initialize a new list.
 *
 * The returned list MUST be destroyed by caller through list_destroy().
 *
 * @param fp_free  call-back function which destroys app-data in nodes
 * @return On success, return a pointer to the new list.
 * @return On failure, return null.
 */
extern t_list_ptr list_new(t_listfunc_free_appdata fp_free);

/**
 * @brief Destroy this list and clear inner data through list_clean().
 *
 * @param pThis  pointer to this list
 *
 * @note The app-data in each node is also destroyed
 *       by the user function which registered by list_init() or list_new().
 *
 * @see list_clean()
 */
extern void list_destroy(t_list_ptr pThis);


/**
 * @brief Initializes this list.
 * @param pThis   pointer to this list
 * @param fp_free  call-back function which destroy app-data in nodes
 */
extern void list_init(t_list_ptr pThis, t_listfunc_free_appdata fp_free);

/**
 * @brief Whether this list has a call-back function which destroy
 *        app-data in nodes.
 * @param pThis  pointer to this list
 * @return Return true if this list is initialized with a non-null
 *         fp_free argument.
 * @see list_init()
 */
extern bool list_has_freefunc(t_list_ptr pThis);

/**
 * @brief Clean and empty a list, and destroy the app-data.
 *
 * @param pThis  pointer to this list
 *
 * @note The app-data in each node is also destroyed
 *       by the user function which has registered by list_init() or list_new().
 *
 * @see list_destroy()
 * @see list_clean_without_appdata()
 */
extern void list_clean(t_list_ptr pThis);

/**
 * @brief Clean and empty a list without destroying the app-data in the node.
 *
 * @param pThis  pointer to this list
 * @note Before call this function, caller MUST firstly save all app-data
 *       in nodes by some manner, and then destroy them.
 * @see list_clean()
 */
extern void list_clean_without_appdata(t_list_ptr pThis);

/**
 * @brief  Check whether this list is empty.
 * @param pThis  pointer to this list
 * @return return true if this list has no any elements,
 *         that is list_size() returns 0.
 * @see list_size()
 */
extern bool list_is_empty(t_list_ptr pThis);

/**
 * @brief Get the number of elements in this list.
 *
 * @param pThis  pointer to this list
 * @return the number of elements in this list.
 * @see list_is_emtpy()
 */
extern int list_size(t_list_ptr pThis);

/**
 * @brief Type of callback functions for traverse a list.
 * @param app_data  the app-data store in a list node
 * @param user_data pointer to any user data for pass some information
 *    to/from this user function. Its usage and memory are owned by user.
 * @return Return 0 to continue visiting the next node in list.
 * @return Return a non-zero value to break the traversal.
 *
 * @see list_foreach, list_foreach_reverse
 */
typedef int (*t_listfunc_visit_appdata)(t_list_app_value app_data, void* user_data);

/**
 * @brief Forward traverse the list (from first to last).
 *
 * Execute a user's action(function) on the app-data in
 * each element of this list.
 * <p>
 * The whole traversal will break if the user's function
 * returns a non-zero value.
 *
 * @param pThis     pointer to this list
 * @param fp_visit  pointer to a function which access each element
 * @param user_data pointer to any user data for pass some information
 *    to/from this user function. Its usage and memory are owned by user.
 *    This parameter will be pass to fp_visit.
 *
 * @return Return 0 if each element has been visited.
 * @return Return the non-zero value from user's action
 *   if whole traversal are broken on one element.
 */
extern int list_foreach(t_list_ptr pThis, t_listfunc_visit_appdata fp_visit, void* user_data);

/**
 * @brief Backward traverse the list (from last to first).
 *
 * Execute a user's action(function) on the app-data in
 * each element of this list.
 * <p>
 * The whole traversal will break if the user's function
 * returns a non-zero value.
 *
 * @param pThis     pointer to this list
 * @param fp_visit  pointer to a function which access each element
 * @param user_data pointer to any user data for pass some information
 *    to/from this user function. Its usage and memory are owned by user.
 *    This parameter will be pass to fp_func.
 *
 * @return Return 0 if each element has been visited.
 * @return Return the non-zero value from user's action
 *   if whole traversal are broken on one element.
 */
extern int list_foreach_reverse(t_list_ptr pThis, t_listfunc_visit_appdata fp_visit, void* user_data);

/**
 * @brief Get the app-data stored in the specified node.
 *
 * @param pThis pointer this list
 * @param index index of the node, valid range is [0, length-1]
 * @return Return NULL if this list is empty or the index is invalid,
 * otherwise, return the app-data stored in the (index+1)th element.
 */
extern t_list_app_value list_get_value(t_list_ptr pThis, int index);

/**
 * @brief Get the app-data stored in the first list node.
 *
 * @param pThis pointer this list
 * @return Return NULL if this list is empty,
 * otherwise, return the app-data stored in first element.
 */
extern t_list_app_value  list_get_first_value(t_list_ptr pThis);

/**
 * @brief Get the app-data stored in the last list node.
 *
 * @param pThis pointer this list
 * @return Return NULL if this list is empty,
 * otherwise, return the app-data stored in last element.
 */
 extern t_list_app_value  list_get_last_value(t_list_ptr pThis);

/**
 * @brief Converts this list to an app-data array.
 *
 * This function create a new array which element is the app-data.
 *
 * @param pThis pointer this list
 * @return  On success, return a pointer to the first element of the new
 *     array which length just is list_size().
 * @return On failure, or this list is empty, returns a null pointer.
 *
 * @note The array **MUST** be deallocated with free() by caller.
 *
 * @note The order of all elements in array is same as in list.
 */
extern t_list_app_value* list_to_array(t_list_ptr pThis);

/**
 * @brief Appends a new element as the last node of this list
 *
 * @param pThis pointer to this list
 * @param pAppData pointer to the app-data stored in new node
 * @return
 *   On success, return a pointer to the new element which store 'pAppData'.
 *   On failure, returns a null pointer.
 */
extern t_list_node* list_append(t_list_ptr pThis, t_list_app_value pAppData);

/**
 * @brief Prepends a new element as the first node of this list
 *
 * @param pThis pointer to this list
 * @param pAppData pointer to the app-data stored in new node
 * @return
 *   On success, return a pointer to the new element which store 'pAppData'.
 *   On failure, returns a null pointer.
 */
extern t_list_node* list_prepend(t_list_ptr pThis, t_list_app_value pAppData);

/**
 * @brief Remove the specified node from this list.
 *        The app-data in node will be destroyed by user-defined
 *        t_listfunc_free_appdata function that registered by list_init().
 * @param pThis  pointer to this list
 * @param nodeTobeRemove  pointer to the node tobe removed
 *
 * @return Return the app-data stored in specified node,
 *         or return NULL if the node doesn't exist in this list.
 * @warning If t_listfunc_free_appdata function that registered by list_init()
 *     is NOT NULL, the app-data in this node will be automatically destroyed
 *     by the t_listfunc_free_appdata function.
 *     So, DON'T use the return value!!!!
 */
extern t_list_app_value list_remove(t_list_ptr pThis, t_list_node_ptr nodeTobeRemove);

/**
 * @brief Remove the first node of this list.
 * @param pThis  pointer to this list
 * @return Return the app-data stored in first element,
 *         or return NULL if this list is empty.
 * @warning If t_listfunc_free_appdata function that registered by list_init()
 *     is NOT NULL, the app-data in this node will be automatically destroyed
 *     by the t_listfunc_free_appdata function.
 *     So, DON'T use the return value!!!!
 */
extern t_list_app_value list_remove_first(t_list_ptr pThis);

/**
 * @brief Remove the last node of this list.
 * @param pThis  pointer to this list
 * @return Return the app-data stored in last element,
 *         or return NULL if this list is empty.
 * @warning If a t_listfunc_free_appdata function that registered by list_init()
 *     is NOT NULL, the app-data in this node will be automatically destroyed
 *     by the t_listfunc_free_appdata function.
 *     So, DON'T use the return value!!!!
 */
extern t_list_app_value list_remove_last(t_list_ptr pThis);

/**
 * @brief Remove the list nodes which subscript is in range
 *        [indexFirst , indexEnd).
 *        The app-data in this node will be destroyed by user-defined
 *        t_listfunc_free_appdata function that registered by list_init().
 * @param pThis  pointer to this list
 * @param indexFirst  subscript of the first node should be removed
 * @param indexEnd    next subscript of the last node should be removed
 * @return Return the number of elements removed.
 * @note  If either indexFirst or indexEnd is less than 0,
 *        no any nodes will be removed.
 * @note  If indexFirst is greater than or equals to indexEnd,
 *        no any nodes will be removed.
 * @note  If indexEnd is greater than or equals to list_size(), then
 *        all nodes in range [indexFirst, list_size) will be removed.
 */
extern int list_remove_range(t_list_ptr pThis, int indexFirst, int indexEnd);


/**
 * @brief Type of callback functions for predication on app-data.
 * @param app_data  the app-data store in a list node
 * @param user_data pointer to any user data for pass some information
 *    to/from this user function. Its usage and memory are owned by user.
 * @return Return true if the predication holds for app-data.
 *
 * @see list_remove_if()
 */
typedef bool (*t_listfunc_predicate)(t_list_app_value app_data, void* user_data);

/**
 * @brief Remove all nodes that satisfy the predicate.
 *        The app-data in these nodes will be destroyed by user-defined
 *        t_listfunc_free_appdata function that registered by list_init().
 * @param pThis  pointer to this list
 * @param fp_predicate  user-defined predicate function which returns
 *      true if the node should be removed.
 *      It's first argument indicates the app-data stored in list node, and
 *      its second argument
 * @param user_data pointer to any user data for pass some information
 *    to/from this user function. Its usage and memory are owned by user.
 *    This parameter will be pass to fp_predicate.
 *
 * @return Return the number of elements removed.
 */
extern int list_remove_if(t_list_ptr pThis,  t_listfunc_predicate fp_predicate, void* user_data);

/// @}
// -----------------------------------------------------------------------


// -----------------------------------------------------------------------
/// @name API of class list-iterator
/// @{


/// Initialize a list iterator
#define LIST_ITERATOR_INIT(pIter, pList) list_iterator_init(pIter, pList)

/// Macros for traversal from first to last: INIT, BEGIN, END, NEXT.
/// Prefer list_foreach() if it can meet your requirements.
#define LIST_ITERATOR_BEGIN(pIter)   ((pIter)->begin(pIter))

/// Macros for traversal from first to last: INIT, BEGIN, END, NEXT.
/// Prefer list_foreach() if it can meet your requirements.
#define LIST_ITERATOR_END(pIter)     ((pIter)->end(pIter))

/// Macros for traversal from first to last: INIT, BEGIN, END, NEXT.
/// Prefer list_foreach() if it can meet your requirements.
#define LIST_ITERATOR_NEXT(pIter)    ((pIter)->next(pIter))


/// Macros for traversal from last to first: INIT, RBEGIN, REND, PREV.
/// Prefer list_foreach_reverse() if it can meet your requirements.
#define LIST_ITERATOR_RBEGIN(pIter)  ((pIter)->rbegin(pIter))

/// Macros for traversal from last to first: INIT, RBEGIN, REND, PREV.
/// Prefer list_foreach_reverse() if it can meet your requirements.
#define LIST_ITERATOR_REND(pIter)    ((pIter)->rend(pIter))

/// Macros for traversal from last to first: INIT, RBEGIN, REND, PREV.
/// Prefer list_foreach_reverse() if it can meet your requirements.
#define LIST_ITERATOR_PREV(pIter)    ((pIter)->prev(pIter))


/**
 * @brief  Class List-Iterator for bi-direction traversal on a list.
 */
typedef struct list_iterator {
// private :
    t_list_ptr      pList;          //!< the list tobe visited
    t_list_node_ptr pCurrentNode;   //!< current node

// public:
// three operations for traverse the list in forward

    /// Return a pointer to the first node of list, or null when list is empty.
    ///
    /// This method is used for forward traversal a list.
    /// @see end, next
    t_list_node_ptr (* begin)(struct list_iterator* pThis);

    /// Return a pointer to next node of last node.
    ///
    /// This method is used for forward traversal a list.
    /// The traverse SHOULD stop once next(pThis) == end(pThis).
    /// @see begin, next
    t_list_node_ptr (* end)(struct list_iterator* pThis);

    /// Return a pointer to next node of current node.
    ///
    /// This method is used for forward traversal a list.
    /// For last node, this operator return end(pThis).
    /// @see begin, end
    t_list_node_ptr (* next)(struct list_iterator* pThis);

// three operations for traverse the list in backward

    /// Return a pointer to the last node of list, or null when list is empty.
    ///
    /// This method is used for backward traversal a list.
    /// @see rend, prev
    t_list_node_ptr (* rbegin)(struct list_iterator* pThis);

    /// Return a pointer to previous node of first node.
    ///
    /// This method is used for backward traversal a list.
    /// The traverse SHOULD stop once prev(pThis) == rend(pThis).
    /// @see rbegin, prev
    t_list_node_ptr (* rend)(struct list_iterator* pThis);

    /// Return a pointer to previous node of current node
    ///
    /// This method is used for backward traversal a list.
    /// For first node, this operator return rend(pThis).
    /// @see rbegin, rend
    t_list_node_ptr (* prev)(struct list_iterator* pThis);

} t_list_iterator;


/**
 * @brief Initialize a list iterator.
 * @param pThis   pointer to this iterator
 * @param pList   pointer to the list tobe traversed
 * @see The first usage is tree_dump() in tree_traverse.c.
 * @attention PLEASE use LIST_ITERATOR_INIT(pThis, pList).
 */
extern void list_iterator_init(t_list_iterator * pThis, t_list_ptr pList);

/// @}
// -----------------------------------------------------------------------


AMCC_DECL_END

#endif  // #ifndef AMCC_LIST_H
